﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Numerics;

namespace BitcoinLibrary
{
    /**
    * A BlockChain holds a series of {@link Block} objects, links them together, and knows how to verify that the
    * chain follows the rules of the {@link NetworkParameters} for this chain.<p>
    *
    * A BlockChain requires a {@link Wallet} to receive transactions that it finds during the initial download. However,
    * if you don't care about this, you can just pass in an empty wallet and nothing bad will happen.<p>
    *
    * A newly constructed BlockChain is empty. To fill it up, use a {@link Peer} object to download the chain from the
    * network.<p>
    *
    * <b>Notes</b><p>
    *
    * The 'chain' can actually be a tree although in normal operation it can be thought of as a simple list. In such a
    * situation there are multiple stories of the economy competing to become the one true consensus. This can happen
    * naturally when two miners solve a block within a few seconds of each other, or it can happen when the chain is
    * under attack.<p>
    *
    * A reference to the head block of every chain is stored. If you can reach the genesis block by repeatedly walking
    * through the prevBlock pointers, then we say this is a full chain. If you cannot reach the genesis block we say it is
    * an orphan chain.<p>
    *
    * Orphan chains can occur when blocks are solved and received during the initial block chain download,
    * or if we connect to a peer that doesn't send us blocks in order.
    */
    public class BlockChain
    {
        //private static readonly Logger log = LoggerFactory.getLogger(BlockChain.class);

        /** Keeps a map of block hashes to StoredBlocks. */
        protected BlockStore blockStore;

        /**
        * Tracks the top of the best known chain.<p>
        *
        * Following this one down to the genesis block produces the story of the economy from the creation of BitCoin
        * until the present day. The chain head can change if a new set of blocks is received that results in a chain of
        * greater work than the one obtained by following this one down. In that case a reorganize is triggered,
        * potentially invalidating transactions in our wallet.
        */
        protected StoredBlock chainHead;

        protected readonly NetworkParameters param;
        protected readonly Wallet wallet;

        // Holds blocks that we have received but can't plug into the chain yet, eg because they were created whilst we
        // were downloading the block chain.
        private readonly List<Block> unconnectedBlocks = new List<Block>();

        /**
        * Constructs a BlockChain connected to the given wallet and store. To obtain a {@link Wallet} you can construct
        * one from scratch, or you can deserialize a saved wallet from disk using {@link Wallet#loadFromFile(java.io.File)}
        * <p>
        *
        * For the store you can use a {@link MemoryBlockStore} if you don't care about saving the downloaded data, or a
        * {@link BoundedOverheadBlockStore} if you'd like to ensure fast startup the next time you run the program.
        */
        public BlockChain(NetworkParameters param, Wallet wallet, BlockStore blockStore)
        {
            try
            {
                this.blockStore = blockStore;
                chainHead = blockStore.getChainHead();
                // TODO: log.info("chain head is:\n{}", chainHead.getHeader());
            }
            catch (Exception e)
            {
                throw e;
            }

            this.param = param;
            this.wallet = wallet;
        }

        /**
        * Processes a received block and tries to add it to the chain. If there's something wrong with the block an
        * exception is thrown. If the block is OK but cannot be connected to the chain at this time, returns false.
        * If the block can be connected to the chain, returns true.
        */
        public /*TODO: synchronized*/ bool add(Block block)
        {
            try
            {
                return add(block, true);
            }
            catch (Exception e)
            {
                // TODO: Figure out a better way to propagate this exception to the user.
                throw e;
            }
        }

        // Stat counters.
        private DateTime statsLastTime = DateTime.Now;    // TODO: System.currentTimeMillis();
        private long statsBlocksAdded;

        private /* TODO: synchronized */ bool add(Block block, bool tryConnecting)
        {
            if (DateTime.Now - statsLastTime > TimeSpan.FromMilliseconds(1000))
            {
                // More than a second passed since last stats logging.
                // TODO: log.info("{} blocks per second", statsBlocksAdded);
                statsLastTime = DateTime.Now;//System.currentTimeMillis();
                statsBlocksAdded = 0;
            }

            // We check only the chain head for double adds here to avoid potentially expensive block chain misses.
            if (block.Equals(chainHead.getHeader()))
            {
                // Duplicate add of the block at the top of the chain, can be a natural artifact of the download process.
                return true;
            }

            // Prove the block is internally valid: hash is lower than target, merkle root is correct and so on.
            try
            {
                block.verify();
            }
            catch (VerificationException e)
            {
                //log.error("Failed to verify block:", e);
                //log.error(block.toString());
                throw e;
            }

            // Try linking it to a place in the currently known blocks.
            StoredBlock storedPrev = blockStore.get(block.getPrevBlockHash());

            if (storedPrev == null)
            {
                // We can't find the previous block. Probably we are still in the process of downloading the chain and a
                // block was solved whilst we were doing it. We put it to one side and try to connect it later when we
                // have more blocks.
                // TODO: log.warn("Block does not connect: {}", block.getHashAsString());
                unconnectedBlocks.Add(block);
                return false;
            }
            else
            {
                // It connects to somewhere on the chain. Not necessarily the top of the best known chain.
                //
                // Create a new StoredBlock from this block. It will throw away the transaction data so when block goes
                // out of scope we will reclaim the used memory.
                StoredBlock newStoredBlock = storedPrev.build(block);
                checkDifficultyTransitions(storedPrev, newStoredBlock);
                blockStore.put(newStoredBlock);
                // block.transactions may be null here if we received only a header and not a full block. This does not
                // happen currently but might in future if getheaders is implemented.
                connectBlock(newStoredBlock, storedPrev, block.transactions);
            }

            if (tryConnecting)
                tryConnectingUnconnected();

            statsBlocksAdded++;
            return true;
        }

        private void connectBlock(StoredBlock newStoredBlock, StoredBlock storedPrev, List<Transaction> newTransactions)
        {
            if (storedPrev.Equals(chainHead))
            {
                // This block connects to the best known block, it is a normal continuation of the system.
                setChainHead(newStoredBlock);
                // TODO: log.info("Chain is now {} blocks high", chainHead.getHeight());
                if (newTransactions != null)
                    sendTransactionsToWallet(newStoredBlock, NewBlockType.BEST_CHAIN, newTransactions);
            }
            else
            {
                // This block connects to somewhere other than the top of the best known chain. We treat these differently.
                //
                // Note that we send the transactions to the wallet FIRST, even if we're about to re-organize this block
                // to become the new best chain head. This simplifies handling of the re-org in the Wallet class.
                bool haveNewBestChain = newStoredBlock.moreWorkThan(chainHead);
                if (haveNewBestChain)
                {
                    // TODO: log.info("Block is causing a re-organize");
                }
                else
                {
                    StoredBlock splitPoint = findSplit(newStoredBlock, chainHead);
                    String splitPointHash =
                    splitPoint != null ? splitPoint.getHeader().getHashAsString() : "?";
                    // TODO: log.info("Block forks the chain at {}, but it did not cause a reorganize:\n{}",
                    //splitPointHash, newStoredBlock);
                }

                // We may not have any transactions if we received only a header. That never happens today but will in
                // future when getheaders is used as an optimization.
                if (newTransactions != null)
                {
                    sendTransactionsToWallet(newStoredBlock, NewBlockType.SIDE_CHAIN, newTransactions);
                }

                if (haveNewBestChain)
                    handleNewBestChain(newStoredBlock);
            }
        }

        /**
        * Called as part of connecting a block when the new block results in a different chain having higher total work.
        */
        private void handleNewBestChain(StoredBlock newChainHead)
        {
            // This chain has overtaken the one we currently believe is best. Reorganize is required.
            //
            // Firstly, calculate the block at which the chain diverged. We only need to examine the
            // chain from beyond this block to find differences.
            StoredBlock splitPoint = findSplit(newChainHead, chainHead);
            // TODO: log.info("Re-organize after split at height {}", splitPoint.getHeight());
            //log.info("Old chain head: {}", chainHead.getHeader().getHashAsString());
            //log.info("New chain head: {}", newChainHead.getHeader().getHashAsString());
            //log.info("Split at block: {}", splitPoint.getHeader().getHashAsString());
            // Then build a list of all blocks in the old part of the chain and the new part.
            List<StoredBlock> oldBlocks = getPartialChain(chainHead, splitPoint);
            List<StoredBlock> newBlocks = getPartialChain(newChainHead, splitPoint);
            // Now inform the wallet. This is necessary so the set of currently active transactions (that we can spend)
            // can be updated to take into account the re-organize. We might also have received new coins we didn't have
            // before and our previous spends might have been undone.
            wallet.reorganize(oldBlocks, newBlocks);
            // Update the pointer to the best known block.
            setChainHead(newChainHead);
        }

        /**
        * Returns the set of contiguous blocks between 'higher' and 'lower'. Higher is included, lower is not.
        */
        private List<StoredBlock> getPartialChain(StoredBlock higher, StoredBlock lower)
        {
            Debug.Assert(higher.getHeight() > lower.getHeight());
            //LinkedList<StoredBlock> results = new LinkedList<StoredBlock>();
            List<StoredBlock> results = new List<StoredBlock>();
            StoredBlock cursor = higher;
            while (true)
            {
                // TODO: ok? results.add(cursor);
                results.Add(cursor);
                cursor = cursor.getPrev(blockStore);
                Debug.Assert(cursor != null, "Ran off the end of the chain");
                if (cursor.Equals(lower)) break;
            }
            return results;
        }

        /**
        * Locates the point in the chain at which newStoredBlock and chainHead diverge. Returns null if no split point was
        * found (ie they are part of the same chain).
        */
        private StoredBlock findSplit(StoredBlock newChainHead, StoredBlock chainHead)
        {
            StoredBlock currentChainCursor = chainHead;
            StoredBlock newChainCursor = newChainHead;
            // Loop until we find the block both chains have in common. Example:
            //
            // A -> B -> C -> D
            // \--> E -> F -> G
            //
            // findSplit will return block B. chainHead = D and newChainHead = G.
            while (!currentChainCursor.Equals(newChainCursor))
            {
                if (currentChainCursor.getHeight() > newChainCursor.getHeight())
                {
                    currentChainCursor = currentChainCursor.getPrev(blockStore);
                    Debug.Assert(currentChainCursor != null, "Attempt to follow an orphan chain");
                }
                else
                {
                    newChainCursor = newChainCursor.getPrev(blockStore);
                    Debug.Assert(newChainCursor != null, "Attempt to follow an orphan chain");
                }
            }
            return currentChainCursor;
        }

        public enum NewBlockType
        {
            BEST_CHAIN,
            SIDE_CHAIN
        }

        private void sendTransactionsToWallet(StoredBlock block, NewBlockType blockType,
        List<Transaction> newTransactions)
        {
            // Scan the transactions to find out if any mention addresses we own.
            foreach (Transaction tx in newTransactions)
            {
                try
                {
                    scanTransaction(block, tx, blockType);
                }
                catch (ScriptException e)
                {
                    // We don't want scripts we don't understand to break the block chain,
                    // so just note that this tx was not scanned here and continue.
                    // TODO: log.warn("Failed to parse a script: " + e.toString());
                }
            }
        }

        private void setChainHead(StoredBlock chainHead)
        {
            this.chainHead = chainHead;
            try
            {
                blockStore.setChainHead(chainHead);
            }
            catch (BlockStoreException e)
            {
                throw e;
            }
        }

        /**
        * For each block in unconnectedBlocks, see if we can now fit it on top of the chain and if so, do so.
        */
        private void tryConnectingUnconnected()
        {
            // For each block in our unconnected list, try and fit it onto the head of the chain. If we succeed remove it
            // from the list and keep going. If we changed the head of the list at the end of the round try again until
            // we can't fit anything else on the top.
            int blocksConnectedThisRound;
            do
            {
                blocksConnectedThisRound = 0;

                var iter = unconnectedBlocks.GetEnumerator();
                while (iter.MoveNext())
                {
                    Block block = iter.Current;
                    // Look up the blocks previous.
                    StoredBlock prev = blockStore.get(block.getPrevBlockHash());
                    if (prev == null)
                    {
                        // This is still an unconnected/orphan block.
                        continue;
                    }
                    // Otherwise we can connect it now.
                    // False here ensures we don't recurse infinitely downwards when connecting huge chains.
                    add(block, false);
                    // TODO: fix? iter.remove();
                    blocksConnectedThisRound++;
                }
                if (blocksConnectedThisRound > 0)
                {
                    // TODO: log.info("Connected {} floating blocks.", blocksConnectedThisRound);
                }
            } while (blocksConnectedThisRound > 0);
        }

        /**
        * Throws an exception if the blocks difficulty is not correct.
        */
        private void checkDifficultyTransitions(StoredBlock storedPrev, StoredBlock storedNext)
        {
            Block prev = storedPrev.getHeader();
            Block next = storedNext.getHeader();
            // Is this supposed to be a difficulty transition point?
            if ((storedPrev.getHeight() + 1) % param.interval != 0)
            {
                // No ... so check the difficulty didn't actually change.
                if (next.getDifficultyTarget() != prev.getDifficultyTarget())
                    throw new VerificationException("Unexpected change in difficulty at height " + storedPrev.getHeight() +
                        //": " + Long.toHexString(next.getDifficultyTarget()) + " vs " +
                    ": " + next.getDifficultyTarget().ToString("X") + " vs " +
                        //Long.toHexString(prev.getDifficultyTarget()));
                    prev.getDifficultyTarget().ToString("X"));
                return;
            }

            // We need to find a block far back in the chain. It's OK that this is expensive because it only occurs every
            // two weeks after the initial block chain download.
            long now = Utils.ConvertToTimestamp(DateTime.Now);  //System.currentTimeMillis();
            StoredBlock cursor = blockStore.get(prev.getHash());
            for (int i = 0; i < param.interval - 1; i++)
            {
                if (cursor == null)
                {
                    // This should never happen. If it does, it means we are following an incorrect or busted chain.
                    throw new VerificationException("Difficulty transition point but we did not find a way back to the genesis block.");
                }
                cursor = blockStore.get(cursor.getHeader().getPrevBlockHash());
            }
            // TODO: log.info("Difficulty transition traversal took {}msec", System.currentTimeMillis() - now);

            Block blockIntervalAgo = cursor.getHeader();
            int timespan = (int)(prev.getTime() - blockIntervalAgo.getTime());
            // Limit the adjustment step.
            if (timespan < param.targetTimespan / 4)
                timespan = param.targetTimespan / 4;
            if (timespan > param.targetTimespan * 4)
                timespan = param.targetTimespan * 4;

            BigInteger newDifficulty = Utils.decodeCompactBits(blockIntervalAgo.getDifficultyTarget());
            newDifficulty = newDifficulty * new BigInteger(timespan);
            newDifficulty = newDifficulty * new BigInteger(param.targetTimespan);

            if (newDifficulty.CompareTo(param.proofOfWorkLimit) > 0)
            {
                // TODO: log.warn("Difficulty hit proof of work limit: {}", newDifficulty.toString(16));
                newDifficulty = param.proofOfWorkLimit;
            }

            int accuracyBytes = (int)(next.getDifficultyTarget() >> 24) - 3;   // TODO: >>>
            BigInteger receivedDifficulty = next.getDifficultyTargetAsInteger();

            // The calculated difficulty is to a higher precision than received, so reduce here.
            // TODO: BigInteger mask = new BigInteger(0xFFFFFFL).shiftLeft(accuracyBytes * 8);
            BigInteger mask = new BigInteger(0xFFFFFFL) << (accuracyBytes * 8);
            //newDifficulty = newDifficulty.and(mask);
            newDifficulty = newDifficulty & mask;

            if (newDifficulty.CompareTo(receivedDifficulty) != 0)
                throw new VerificationException("Network provided difficulty bits do not match what was calculated: " +
                receivedDifficulty.ToString("X") + " vs " + newDifficulty.ToString("2X"));
        }

        private void scanTransaction(StoredBlock block, Transaction tx, NewBlockType blockType)
        {
            bool shouldReceive = false;
            foreach (TransactionOutput output in tx.outputs)
            {
                // TODO: Handle more types of outputs, not just regular to address outputs.
                if (output.getScriptPubKey().isSentToIP()) return;
                // This is not thread safe as a key could be removed between the call to isMine and receive.
                if (output.isMine(wallet))
                {
                    shouldReceive = true;
                }
            }

            // Coinbase transactions don't have anything useful in their inputs (as they create coins out of thin air).
            if (!tx.isCoinBase())
            {
                foreach (TransactionInput i in tx.inputs)
                {
                    byte[] pubkey = i.getScriptSig().getPubKey();
                    // This is not thread safe as a key could be removed between the call to isPubKeyMine and receive.
                    if (wallet.isPubKeyMine(pubkey))
                    {
                        shouldReceive = true;
                    }
                }
            }

            if (shouldReceive)
                wallet.receive(tx, block, blockType);
        }

        /**
        * Returns the block at the head of the current best chain. This is the block which represents the greatest
        * amount of cumulative work done.
        */
        public /*synchronized */ StoredBlock getChainHead()
        {
            return chainHead;
        }

        /**
        * Returns the most recent unconnected block or null if there are none. This will all have to change.
        */
        public /*synchronized*/ Block getUnconnectedBlock()
        {
            if (unconnectedBlocks.Count == 0)
                return null;
            return unconnectedBlocks[unconnectedBlocks.Count - 1];
        }
    }
}
